/**
 * @Title: QuickSort_SelectKey.java
 * @Package com.adamjwh.sort.quicksort
 * @Description: 
 * @author adamjwh
 * @date 2018年6月24日
 * @version V1.0
 */
package com.adamjwh.sort.quicksort;

import java.util.Random;

/**
 * @ClassName: QuickSort_SelectKey
 * @Description: 快排优化——选取基准
 * @author adamjwh
 * @date 2018年6月24日
 *
 */
public class QuickSort_SelectKey {
	
	/**
	 * 
	 * @Title: selectPivot
	 * @Description: 选取序列最左边的元素为基准值
	 * @param @param arr
	 * @param @param low
	 * @param @param high
	 * @param @return    参数
	 * @return int    返回类型
	 * @throws
	 */
	public static int selectPivot(int[] arr, int low, int high) {
		return arr[low];
	}

	/**
	 * 
	 * @Title: selectPivotRandom
	 * @Description: 随机选取基准值
	 * @param @param arr
	 * @param @param low
	 * @param @param high
	 * @param @return    返回基准值
	 * @return int    返回类型
	 * @throws
	 */
	public static int selectPivotRandom(int[] arr, int low, int high) {
		Random random = new Random();
		int pivot =random.nextInt(high-low+1) + low;	//随机生成low->high中的随机值
		swap(arr[pivot], arr[low]);	//将枢纽位置元素和low位置元素互换，此时可以和普通快排一样调用划分函数
		return arr[low];
	}
	
	/**
	 * 
	 * @Title: SelectPivotMedianOfThree
	 * @Description: 三数取中法选取基准值（取待排序序列中low、mid、high三个位置上的数据，选取他们排序后中间的那个数据作为枢轴）
	 * @param @param arr
	 * @param @param low
	 * @param @param high
	 * @param @return    返回基准值
	 * @return int    返回类型
	 * @throws
	 */
	public static int SelectPivotMedianOfThree(int[] arr, int low, int high) {
		int mid = ((high-low) >> 1) + low;	//计算数组的中见下标
		
		if(arr[low] > arr[high]) {
			swap(arr[low], arr[high]);
		}
		if(arr[mid] > arr[high]) {
			swap(arr[mid], arr[high]);
		}
		if(arr[mid] > arr[low]) {	//取中间值，low的位置上保存这三个位置的中间值，分割时可以直接使用low位置的元素作为枢轴 
			swap(arr[low], arr[mid]);
		}
		//此时 arr[mid] <= arr[low] <= arr[high]
		return arr[low];
	}
	
	/**
	 * 
	 * @Title: swap
	 * @Description: 工具方法——交换元素
	 * @param @param a
	 * @param @param b    参数
	 * @return void    返回类型
	 * @throws
	 */
	private static void swap(int a, int b) {
		int t = a;
		a = b;
		b = t;
	}
	
}
